{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Operations to Make String Sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math #string #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学 #字符串 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: makeStringSorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使字符串有序的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> （<strong>下标从 0 开始</strong>）。你需要对 <code>s</code> 执行以下操作直到它变为一个有序字符串：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>找到 <strong>最大下标</strong> <code>i</code> ，使得 <code>1 &lt;= i &lt; s.length</code> 且 <code>s[i] &lt; s[i - 1]</code> 。</li>\n",
    "\t<li>找到 <strong>最大下标</strong> <code>j</code> ，使得 <code>i &lt;= j &lt; s.length</code> 且对于所有在闭区间 <code>[i, j]</code> 之间的 <code>k</code> 都有 <code>s[k] &lt; s[i - 1]</code> 。</li>\n",
    "\t<li>交换下标为 <code>i - 1</code>​​​​ 和 <code>j</code>​​​​ 处的两个字符。</li>\n",
    "\t<li>将下标 <code>i</code> 开始的字符串后缀反转。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你返回将字符串变成有序的最少操作次数。由于答案可能会很大，请返回它对 <code>10<sup>9</sup> + 7</code> <strong>取余</strong> 的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"cba\"\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>模拟过程如下所示：\n",
    "操作 1：i=2，j=2。交换 s[1] 和 s[2] 得到 s=\"cab\" ，然后反转下标从 2 开始的后缀字符串，得到 s=\"cab\" 。\n",
    "操作 2：i=1，j=2。交换 s[0] 和 s[2] 得到 s=\"bac\" ，然后反转下标从 1 开始的后缀字符串，得到 s=\"bca\" 。\n",
    "操作 3：i=2，j=2。交换 s[1] 和 s[2] 得到 s=\"bac\" ，然后反转下标从 2 开始的后缀字符串，得到 s=\"bac\" 。\n",
    "操作 4：i=1，j=1。交换 s[0] 和 s[1] 得到 s=\"abc\" ，然后反转下标从 1 开始的后缀字符串，得到 s=\"acb\" 。\n",
    "操作 5：i=2，j=2。交换 s[1] 和 s[2] 得到 s=\"abc\" ，然后反转下标从 2 开始的后缀字符串，得到 s=\"abc\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"aabaa\"\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>模拟过程如下所示：\n",
    "操作 1：i=3，j=4。交换 s[2] 和 s[4] 得到 s=\"aaaab\" ，然后反转下标从 3 开始的后缀字符串，得到 s=\"aaaba\" 。\n",
    "操作 2：i=4，j=4。交换 s[3] 和 s[4] 得到 s=\"aaaab\" ，然后反转下标从 4 开始的后缀字符串，得到 s=\"aaaab\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"cdbea\"\n",
    "<b>输出：</b>63</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>s = \"leetcodeleetcodeleetcode\"\n",
    "<b>输出：</b>982157772\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 3000</code></li>\n",
    "\t<li><code>s</code>​ 只包含小写英文字母。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-operations-to-make-string-sorted](https://leetcode.cn/problems/minimum-number-of-operations-to-make-string-sorted/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-operations-to-make-string-sorted](https://leetcode.cn/problems/minimum-number-of-operations-to-make-string-sorted/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"cba\"', '\"aabaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        # 求字符串的总共组合数量，用到了那个先验知识\n",
    "        cnt = collections.Counter(s)\n",
    "        cur = math.factorial(len(s))\n",
    "        for v in cnt.values():\n",
    "            cur //= math.factorial(v)\n",
    "\n",
    "        res = 0\n",
    "        for i, v in enumerate(s):\n",
    "            for ke, va in cnt.items():\n",
    "                # 当后续某个字符小于当前字符，累加当前的可能性\n",
    "                # 以上面的描述为例，当b后面出现个a，可以假定当前位置变成a，这种情况下\n",
    "                # 还剩下 (x - 1)个a，y个b，z个c, 组合总数为 ((x - 1) + y + z)! / ((x - 1)! * y! * z!)\n",
    "                # 等同为 (x + y + z)! / (x! * y! * z!) * x / (x + y + z)\n",
    "                # 也就是下面的 cur * va // (len(s) - i)\n",
    "                if ke < v:\n",
    "                    res += cur * va // (len(s) - i)\n",
    "\n",
    "            # 当字符往后移动时，更新当前的可能的组合数，同时更新Counter\n",
    "            cur = cur * cnt[v] // (len(s) - i)\n",
    "            cnt[v] -= 1\n",
    "\n",
    "        return res % (10 ** 9 + 7)\n",
    "\n",
    "# 作者：Rong Fan\n",
    "# 链接：https://leetcode.cn/problems/minimum-number-of-operations-to-make-string-sorted/solutions/728386/bi-jiao-hao-li-jie-de-pythondai-ma-by-se-f4tw/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            top, down = 0, 1\n",
    "            for j in range(26):\n",
    "                choice = chr(j + ord('a'))\n",
    "                if choice < ch and c[choice] > 0:\n",
    "                    top += c[choice]\n",
    "                down *= math.factorial(c[choice])\n",
    "            rhs_length = len(s) - i - 1\n",
    "            ans += top * math.factorial(rhs_length) // down\n",
    "            c[ch] -= 1\n",
    "            ans %= 10**9 + 7\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        # 快速幂，用来计算 x^y mod m\n",
    "        def quickmul(x: int, y: int) -> int:\n",
    "            # Python 有方便的内置函数\n",
    "            return pow(x, y, mod)\n",
    "    \n",
    "        n = len(s)\n",
    "        \n",
    "        # fac[i] 表示 i! mod m\n",
    "        # facinv[i] 表示 i! 在 mod m 意义下的乘法逆元\n",
    "        fac, facinv = [0] * (n + 1), [0] * (n + 1)\n",
    "        fac[0] = facinv[0] = 1\n",
    "        for i in range(1, n):\n",
    "            fac[i] = fac[i - 1] * i % mod\n",
    "            # 使用费马小定理 + 快速幂计算乘法逆元\n",
    "            facinv[i] = quickmul(fac[i], mod - 2)\n",
    "        \n",
    "        # freq 存储每个字符出现的次数\n",
    "        freq = collections.Counter(s)\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            # rank 求出比 s[i] 小的字符数量\n",
    "            rank = sum(occ for ch, occ in freq.items() if ch < s[i])\n",
    "            # 排列个数的分子\n",
    "            cur = rank * fac[n - i - 1] % mod\n",
    "            # 依次乘分母每一项阶乘的乘法逆元\n",
    "            for ch, occ in freq.items():\n",
    "                cur = cur * facinv[occ] % mod\n",
    "            \n",
    "            ans += cur\n",
    "            freq[s[i]] -= 1\n",
    "            if freq[s[i]] == 0:\n",
    "                freq.pop(s[i])\n",
    "        \n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        c = Counter(s)\n",
    "        MOD = 10 ** 9 + 7\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            top, down = 0, 1\n",
    "            for j in range(26):\n",
    "                choice = chr(j + ord('a'))\n",
    "                if choice < ch and c[choice] > 0:\n",
    "                    top += c[choice]\n",
    "                down *= math.factorial(c[choice])\n",
    "            rhs_length = len(s) - i - 1\n",
    "            ans += top * math.factorial(rhs_length) // down\n",
    "            c[ch] -= 1\n",
    "            if ans > MOD:\n",
    "                ans %= MOD\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        def qpow(a, x):\n",
    "            ret = 1\n",
    "            while x:\n",
    "                if x & 1:\n",
    "                    ret = ret * a % p\n",
    "                x >>= 1\n",
    "                a = a * a % p\n",
    "            return ret\n",
    "        \n",
    "        p = 10 ** 9 + 7\n",
    "        ret = 0\n",
    "        n = len(s)\n",
    "        f = 1\n",
    "        \n",
    "        fac = [0] * 3001\n",
    "        fac[1] = 1\n",
    "        fac2 = [0] * 3001\n",
    "        fac2[1] = 1\n",
    "        for i in range(2, 3001):\n",
    "            fac[i] = fac[i - 1] * i % p\n",
    "            fac2[i] = qpow(fac[i], p - 2)\n",
    "        \n",
    "        \n",
    "\n",
    "        def permutations_with_duplicates(n,  k):\n",
    "            cnt[k] += 1\n",
    "            ret = 0\n",
    "            \n",
    "            for i in range(k):\n",
    "                if cnt[i]:\n",
    "                    cnt[i] -= 1\n",
    "                    x = fac[n]\n",
    "                    for j in range(26):\n",
    "                        if cnt[j]:\n",
    "                            x = x * fac2[cnt[j]] % p\n",
    "                    ret = (ret + x) % p\n",
    "                    # print(s, cnt[:6], x, n, k)\n",
    "                    cnt[i] += 1\n",
    "            cnt[k] -= 1\n",
    "            return ret\n",
    "        cnt = [0] * 26 \n",
    "        for i in range(n - 2, -1, -1):\n",
    "            cnt[ord(s[i + 1]) - ord('a')] += 1\n",
    "            ret += permutations_with_duplicates(n - i - 1,  ord(s[i]) - ord('a')) % p\n",
    "        return ret % p"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n = len(s)\n",
    "        fac, invf = [1] * (n + 1), [1] * (n + 1) \n",
    "        for i in range(2, n + 1):\n",
    "            fac[i] = (fac[i - 1] * i) % mod\n",
    "            invf[i] = (invf[i - 1] * pow(i, -1, mod)) % mod\n",
    "        cnt = Counter(s)\n",
    "        ans = 0\n",
    "        for ss in s:\n",
    "            for k in sorted(cnt.keys()):\n",
    "                if k == ss:\n",
    "                    cnt[ss] -= 1\n",
    "                    if cnt[ss] == 0:\n",
    "                        cnt.pop(ss)\n",
    "                    break\n",
    "                tmp1, tmp2 = 0, 1\n",
    "                for kk in cnt:\n",
    "                    if kk == k:\n",
    "                        tmp1 += cnt[kk] - 1\n",
    "                        tmp2 = (tmp2 * invf[cnt[kk] - 1]) % mod\n",
    "                    else:\n",
    "                        tmp1 += cnt[kk]\n",
    "                        tmp2 = (tmp2 * invf[cnt[kk]]) % mod\n",
    "                ans += (fac[tmp1] * tmp2) % mod\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        mod = 10**9 + 7\n",
    "\n",
    "        # 快速幂\n",
    "        def quickmul(x: int, y: int) -> int:\n",
    "            return pow(x, y, mod)\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        fac, facinv = [0] * (n + 1), [0] * (n + 1)\n",
    "        fac[0] = facinv[0] = 1\n",
    "        for i in range(1, n):\n",
    "            fac[i] = fac[i - 1] * i % mod\n",
    "            facinv[i] = quickmul(fac[i], mod - 2)\n",
    "\n",
    "        freq = collections.Counter(s)\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(n - 1):\n",
    "            rank = sum(occ for ch, occ in freq.items() if ch < s[i])\n",
    "            cur = rank * fac[n - i - 1] % mod\n",
    "            for ch, occ in freq.items():\n",
    "                cur = cur * facinv[occ] % mod\n",
    "\n",
    "            ans += cur\n",
    "            freq[s[i]] -= 1\n",
    "            if freq[s[i]] == 0:\n",
    "                freq.pop(s[i])\n",
    "\n",
    "        return ans % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# the described operation makes s into it's previous string\r\n",
    "# in permutation order, thus the problem is equivalent to finding\r\n",
    "# how many strings are lexicologically smallers than s in full permutation\r\n",
    "# let rank(i) = number of letter is in s[i:] which are lexicologically smaller than s[i]\r\n",
    "# let a(i), b(i), ..., z(i) = frequency of a, b, ..., z in s[i:]\r\n",
    "# there will be\r\n",
    "#   rank(i) * (n - i - 1)! / prod(a(i)!, b(i)!, ..., z(i)!)\r\n",
    "# strings, which are same with s[:i], and lexicologically smaller than s\r\n",
    "from functools import reduce\r\n",
    "\r\n",
    "mod = 1000000007\r\n",
    "bit_arr = [0] * 27\r\n",
    "memo = [0] * 3001\r\n",
    "\r\n",
    "def fact(x: int) -> int:\r\n",
    "    if x < 2:\r\n",
    "        return 1\r\n",
    "    if memo[x] == 0:\r\n",
    "        memo[x] = x * fact(x - 1) % mod\r\n",
    "\r\n",
    "    return memo[x]\r\n",
    "\r\n",
    "def lowbit(x: int) -> int:\r\n",
    "    return x & (-x)\r\n",
    "\r\n",
    "def update(idx: int, d: int) -> None:\r\n",
    "    idx += 1\r\n",
    "    while idx < 27:\r\n",
    "        bit_arr[idx] += d\r\n",
    "        idx += lowbit(idx)\r\n",
    "\r\n",
    "def query(idx: int) -> int:\r\n",
    "    ret = 0\r\n",
    "    idx += 1\r\n",
    "    while idx > 0:\r\n",
    "        ret += bit_arr[idx]\r\n",
    "        idx -= lowbit(idx)\r\n",
    "    return ret\r\n",
    "\r\n",
    "def moddiv(nomi: int, deno: int) -> int:\r\n",
    "    return nomi * pow(deno, mod - 2, mod) % mod\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def makeStringSorted(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        res = 0\r\n",
    "        for i in range(27): bit_arr[i] = 0\r\n",
    "        for idx in map(ord, s):\r\n",
    "            update(idx - 97, 1)\r\n",
    "        \r\n",
    "        for i, idx in enumerate(map(ord, s)):\r\n",
    "            res += moddiv(query(idx - 98) * fact(n - i - 1) % mod, \r\n",
    "                reduce(lambda x, y: x * fact(query(y) - query(y - 1)) % mod, range(26), 1))\r\n",
    "            res %= mod\r\n",
    "            update(idx - 97, -1)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1000000007\n",
    "class SegSumTree:\n",
    "    '''\n",
    "    线段树（区间和）\n",
    "    '''\n",
    "    def __init__(self, nums):\n",
    "        n = len(nums)\n",
    "        self.n = n\n",
    "        self.seg = [0] * (n * 4)\n",
    "        self.build(nums, 0, 0, n - 1)\n",
    "\n",
    "    def build(self, nums, node: int, s: int, e: int):\n",
    "        if s == e:\n",
    "            self.seg[node] = nums[s]\n",
    "            return\n",
    "        m = s + (e - s) // 2\n",
    "        self.build(nums, node * 2 + 1, s, m)\n",
    "        self.build(nums, node * 2 + 2, m + 1, e)\n",
    "        self.seg[node] = self.seg[node * 2 + 1] + self.seg[node * 2 + 2]\n",
    "\n",
    "    def change(self, index: int, val: int, node: int, s: int, e: int):\n",
    "        if s == e:\n",
    "            self.seg[node] = val\n",
    "            return\n",
    "        m = s + (e - s) // 2\n",
    "        if index <= m:\n",
    "            self.change(index, val, node * 2 + 1, s, m)\n",
    "        else:\n",
    "            self.change(index, val, node * 2 + 2, m + 1, e)\n",
    "        self.seg[node] = self.seg[node * 2 + 1] + self.seg[node * 2 + 2]\n",
    "\n",
    "    def range(self, left: int, right: int, node: int, s: int, e: int) -> int:\n",
    "        if left == s and right == e:\n",
    "            return self.seg[node]\n",
    "        m = s + (e - s) // 2\n",
    "        if right <= m:\n",
    "            return self.range(left, right, node * 2 + 1, s, m)\n",
    "        if left > m:\n",
    "            return self.range(left, right, node * 2 + 2, m + 1, e)\n",
    "        return self.range(left, m, node * 2 + 1, s, m) + self.range(m + 1, right, node * 2 + 2, m + 1, e)\n",
    "\n",
    "    def update(self, index: int, val: int) -> None:\n",
    "        '''\n",
    "        更新坐标index的值为val\n",
    "        '''\n",
    "        self.change(index, val, 0, 0, self.n - 1)\n",
    "\n",
    "    def sumRange(self, left: int, right: int) -> int:\n",
    "        '''\n",
    "        求区间[left,right]的和\n",
    "        '''\n",
    "        return self.range(left, right, 0, 0, self.n - 1)\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        def MultiInverse(x,mod):\n",
    "            '''\n",
    "            乘法逆元\n",
    "            '''\n",
    "            return pow(x,mod-2,mod)\n",
    "\n",
    "        def BigDivision(x,y,mod):\n",
    "            '''\n",
    "            大数除法x/y\n",
    "            '''\n",
    "            return (x % mod) * MultiInverse(y,mod) % mod\n",
    "        s = [ord(c)-ord('a') for c in s]\n",
    "        #排列数（含重复项）公式\n",
    "        #N = a!/(a1! * a2! *a3!)\n",
    "        #字符串     c           b           a\n",
    "        #计数n      3           2           1\n",
    "        #计数c      1           0           0\n",
    "        #计数b      1           1           0\n",
    "        #计数a      1           1           1\n",
    "        #分子nume   (3-1)!(1+1) (2-1)!1     (1-1)!0\n",
    "        #分母deno   1!1!1!      1!1!        1!\n",
    "        #答案ans    4           1           0\n",
    "        segs = SegSumTree([0]*26)\n",
    "        n = 0\n",
    "        nume = 1\n",
    "        deno = 1\n",
    "        ct = [0]*26\n",
    "        ans = 0\n",
    "        for v in s[::-1]:\n",
    "            if n>0:\n",
    "                nume = nume * n % MOD\n",
    "            n+=1\n",
    "            ct[v]+=1\n",
    "            #使用乘法逆元将除法转为乘法\n",
    "            deno=deno * MultiInverse(ct[v],MOD) % MOD\n",
    "            segs.update(v,ct[v])\n",
    "            if v>0:\n",
    "                nume2 = nume * segs.sumRange(0,v-1)\n",
    "                ans = (ans + nume2 * deno % MOD) % MOD\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# the described operation makes s into it's previous string\r\n",
    "# in permutation order, thus the problem is equivalent to finding\r\n",
    "# how many strings are lexicologically smallers than s in full permutation\r\n",
    "# let rank(i) = number of letter is in s[i:] which are lexicologically smaller than s[i]\r\n",
    "# let a(i), b(i), ..., z(i) = frequency of a, b, ..., z in s[i:]\r\n",
    "# there will be\r\n",
    "#   rank(i) * (n - i - 1)! / prod(a(i)!, b(i)!, ..., z(i)!)\r\n",
    "# strings, which are same with s[:i], and lexicologically smaller than s\r\n",
    "from functools import reduce\r\n",
    "\r\n",
    "mod = 1000000007\r\n",
    "bit_arr = [0] * 27\r\n",
    "f = [0] * 3001\r\n",
    "finv = [0] * 3001\r\n",
    "\r\n",
    "def fact(x: int) -> int:\r\n",
    "    if x < 2:\r\n",
    "        return 1\r\n",
    "    if f[x] == 0:\r\n",
    "        f[x] = x * fact(x - 1) % mod\r\n",
    "\r\n",
    "    return f[x]\r\n",
    "\r\n",
    "def factinv(x: int) -> int:\r\n",
    "    if finv[x] == 0:\r\n",
    "        finv[x] = moddiv(1, fact(x))\r\n",
    "    \r\n",
    "    return finv[x]\r\n",
    "\r\n",
    "def lowbit(x: int) -> int:\r\n",
    "    return x & (-x)\r\n",
    "\r\n",
    "def update(idx: int, d: int) -> None:\r\n",
    "    idx += 1\r\n",
    "    while idx < 27:\r\n",
    "        bit_arr[idx] += d\r\n",
    "        idx += lowbit(idx)\r\n",
    "\r\n",
    "def query(idx: int) -> int:\r\n",
    "    ret = 0\r\n",
    "    idx += 1\r\n",
    "    while idx > 0:\r\n",
    "        ret += bit_arr[idx]\r\n",
    "        idx -= lowbit(idx)\r\n",
    "    return ret\r\n",
    "\r\n",
    "def moddiv(nomi: int, deno: int) -> int:\r\n",
    "    return nomi * pow(deno, mod - 2, mod) % mod\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def makeStringSorted(self, s: str) -> int:\r\n",
    "        n = len(s)\r\n",
    "        res = 0\r\n",
    "        for i in range(27): bit_arr[i] = 0\r\n",
    "        for idx in map(ord, s):\r\n",
    "            update(idx - 97, 1)\r\n",
    "        \r\n",
    "        for i, idx in enumerate(map(ord, s)):\r\n",
    "            res += reduce(lambda x, y: x * y % mod, map(lambda y: factinv(query(y) - query(y - 1)), range(26)),\r\n",
    "                          query(idx - 98) * fact(n - i - 1) % mod)\r\n",
    "            res %= mod\r\n",
    "            update(idx - 97, -1)\r\n",
    "        \r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "MOD = int(1e9) + 7\n",
    "\n",
    "def qpow(x, y):\n",
    "    ret = 1\n",
    "    mul = x\n",
    "\n",
    "    while y:\n",
    "        if y % 2 == 1:\n",
    "            ret = ret * mul % MOD\n",
    "\n",
    "        mul = mul * mul % MOD\n",
    "        y //= 2\n",
    "\n",
    "    return ret\n",
    "\n",
    "@cache\n",
    "def fac(x):\n",
    "    if x == 1:\n",
    "        return 1\n",
    "\n",
    "    return x * fac(x - 1) % MOD\n",
    "\n",
    "@cache\n",
    "def facinv(x):\n",
    "    return qpow(fac(x), MOD - 2)\n",
    "\n",
    "class Solution:\n",
    "    def makeStringSorted(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        cnt = Counter(s)\n",
    "        \n",
    "        ret = 0\n",
    "        for i in range(n - 1):\n",
    "            x = s[i]\n",
    "            repinv = 1\n",
    "            rank = 0\n",
    "            for k, v in cnt.items():\n",
    "                if v > 0:\n",
    "                    repinv *= facinv(v)\n",
    "\n",
    "                if k < x:\n",
    "                    rank += v\n",
    "\n",
    "            ret += ((rank * fac(n - 1 - i)) % MOD * repinv) % MOD\n",
    "            ret %= MOD\n",
    "\n",
    "            cnt[x] -= 1\n",
    "\n",
    "        return ret"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
